Tags: lecture-05, verifying recursion
Will the following code always do what it says? You may assume that numbers is a (possibly empty) array of numbers. The product of zero numbers is defined to be 1. Select all that apply.
def product(numbers):
"""Should return the product of all elements in numbers"""
if len(numbers) == 0:
return 1
else:
return numbers[0] * product(numbers[1:])Yes. The base case is correct, since the product of zero numbers is 1. The recursive call is on a list that is one element shorter, so the recursion always reaches the base case. And if product(numbers[1:]) correctly returns the product of all but the first number, then multiplying it by numbers[0] gives the product of all of the numbers.
Tags: lecture-05, verifying recursion
Will the following code always do what it claims? You may assume that numbers is a (possibly empty) array of numbers. Select all that apply.
def reverse(numbers):
"""Should reverse a given list of numbers."""
if len(numbers) == 0:
return numbers
else:
# numbers[:-1] *slices* the list, creating a new list
# with the same elements as the original, except with
# the last element removed
return reverse(numbers[:-1])No - it does not infinitely recurse, but the result may be incorrect. Each recursive call is on a list that is one element shorter, so the recursion always reaches the base case. But the base case returns an empty list, and each recursive call simply returns what the next call returns, so reverse always returns []. This is wrong for any nonempty list.
Tags: lecture-05, verifying recursion
Consider the following function which attempts to compute the maximum of a list of numbers.
import math
def maximum(numbers):
n = len(numbers)
if n == 0:
return 0
middle = math.floor(n / 2)
return (
maximum(numbers[:middle])
+
maximum(numbers[middle:])
)Is this code guaranteed to work for all non-empty lists?
You should adopt the convention that the maximum of an empty list is \(-\infty\).
2nd option: No: it may recurse infinitely.
Tags: lecture-05, verifying recursion
Consider the code below which claims to compute the maximum of the input array. Adopt the convention that the maximum of an empty array is \(-\infty\).
import math
def maximum(arr, start=0, stop=None):
"""Find the maximum of arr[start:stop]."""
if stop is None:
stop = len(arr)
if stop - start == 0:
return -float('inf')
middle = math.floor((start + stop) / 2)
left = maximum(arr, start, middle)
right = maximum(arr, middle, stop)
if left > right:
return left
else:
return rightWill this code always return the correct answer (the maximum)? If yes, simply say so. If no, describe what might happen (recurse infinitely, return the wrong answer, raise an index error, etc.).
This code will recurse infinitely when called on an array with a single element.
Tags: lecture-05, recursion, verifying recursion
Consider the code below which claims to compute the most common element in the array, returning a pair: the element along with the number of times it appears.
import math
def most_common(arr, start, stop):
"""Attempts to compute the most common element in arr[start:stop]."""
if stop - start == 1:
return (arr[start], 1)
middle = math.floor((start + stop) / 2)
left_value, left_count = most_common(arr, start, middle)
right_value, right_count = most_common(arr, middle, stop)
if left_count > right_count:
return (left_value, left_count)
else:
return (right_value, right_count)You may assume that the function is always called on a non-empty array, and with start = 0 and stop = len(arr). Will this code always return the correct answer (the most common element)?
No: it will run without error, but the element returned may not be the most common element in the array.
It is not true in general that the most common element in the array is the most common in the left or the right. As a simple example, take: [1,1,1,0,0,2,2,2,0,0]. 1 is the most common in the left half, and 2 is the most common in the right half, but 0 is the most common overall.
So even if we assume that most_common(arr, start, middle) finds the most common element in left half of the array, and most_common(arr, middle, stop) finds the most common element in the right of the array, it is not necessarily the case that the most common between them is the overall most common in the array.
You can also quickly see that the code cannot be correct because nowhere is a count greater than one ever returned.
Tags: lecture-05, verifying recursion, binary search
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop
= len(arr) - 1.
new_binary_search may recurse infinitely
Tags: lecture-05, recursion, binary search, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).
True or False: there are input arrays on which new_binary_search will recurse infinitely.
True.
Consider arr = [1, 2] with target = 0. The first call computes middle = 1, and since \(2 > 0\) it recurses with start = 0, stop = 1. There, middle is \(\lceil 1/2 \rceil = 1\) again, and since \(2 > 0\) it makes the same call, start = 0, stop = 1, forever. The problem is that when stop = start + 1, the ceiling gives middle = stop, so the left recursion doesn't shrink the range.
True or False: there are input arrays on which new_binary_search will raise an IndexError because it attempts to access an element of the array which does not exist.
True.
If arr has one element, the first call has start = 0 and stop = 1, so middle is \(\lceil 1/2 \rceil = 1\), and arr[1] doesn't exist. In general, whenever stop = start + 1, the ceiling makes middle = stop, which is outside the range being searched.